题解 CF1360E@洛谷 | 1360E@Codeforces 【Polygon】

拿到这题一头雾水，找找规律。

按照游戏规则，一个数的右侧和下侧必须有数才可能被大炮发射到这里。

看到样例，发现如果去掉最后一行以及最后一列，剩余的所有 $1$ 的右侧或下侧的格子有 $1$，就是可以完成；反之不能。

大胆猜测：除了最右列与最下行，如果每个 $1$ 右侧或下侧都有 $1$，则可以完成；有一个 $1$ 右侧下侧均没有 $1$ 就不能完成。

考试时直接交了，没有证明正确性，发现 PP 了。现在口胡一个，不是特别严谨，可以画画图试着理解：

• 如果一个 $1$ 右侧有 $1$，可以通过左侧大炮发射过来。
• 如果一个 $1$ 下侧有 $1$，可以通过上方大炮发射过来。
• 最右列和最下行一定可以达到。

类似数学归纳法的思想，证明上面的猜测。

代码：

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;

int T, n, a[55][55];

int main() {
	scanf("%d", &T);
	while(T--) {
		scanf("%d", &n);
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=n;j++) {
				char c = getchar();
				while(!isdigit(c)) c = getchar();
				a[i][j] = c - '0';
			}
		}
		bool book = true;
		for(int i=1;i<n;i++) {
			for(int j=1;j<n;j++) {
				if(a[i][j] && !a[i][j+1] && !a[i+1][j]) {
					book = false;
					break;
				}
			}
			if(!book) break;
		}
		if(book) puts("YES");
		else puts("NO");
	}
	return 0;
}